#include <iostream>
using namespace std;
#include <vector>
#include <algorithm>

//vector<vector<int>> fourSum(vector<int>& nums, int target) {
//    sort(nums.begin(), nums.end());
//    size_t n = nums.size();
//
//    vector<vector<int>> vv;
//
//    size_t pos1 = 0;
//
//    while (pos1 < n)
//    {
//        size_t pos2 = pos1 + 1;
//        while (pos2 < n)
//        {
//            size_t left = pos2 + 1;
//            size_t right = nums.size() - 1;
//            // nums[pos1] + nums[pos2] + nums[left] + nums[right] = target
//            // nums[left] + nums[right] = target - nums[pos1] - nums[pos2]
//            while (left < right)
//            {
//                long long sum = (long long)target - nums[pos1] - nums[pos2];
//                if (nums[left] + nums[right] < sum)
//                {
//                    do
//                    {
//                        ++left;
//                    } while (left < right && nums[left] == nums[left - 1]);
//                }
//                else if (nums[left] + nums[right] > sum)
//                {
//                    do
//                    {
//                        --right;
//                    } while (left < right && nums[right] == nums[right + 1]);
//                }
//                else
//                {
//                    vector<int> tmp{ nums[pos1], nums[pos2], nums[left], nums[right] };
//                    vv.push_back(tmp);
//                    do
//                    {
//                        ++left;
//                    } while (left < right && nums[left] == nums[left - 1]);
//                    do
//                    {
//                        --right;
//                    } while (left < right && nums[right] == nums[right + 1]);
//                }
//                
//            }
//            do
//            {
//                ++pos2;
//
//            } while (pos2 < n && nums[pos2] == nums[pos2 - 1]);
//        }
//        do
//        {
//            ++pos1;
//
//        } while (pos1 < n && nums[pos1] == nums[pos1 - 1]);
//    }
//    return vv;
//}
//
//int main()
//{
//    vector<int> v{ 1000000000,1000000000,1000000000,1000000000 };
//    fourSum(v, -294967296);
//
//    return 0;
//}

//
//vector<vector<int>> fourSum(vector<int>& nums, int target) {
//    sort(nums.begin(), nums.end());
//    vector<vector<int>> vv;
//
//    int n = nums.size();
//    for (int i = 0; i < n; )
//    {
//        for (int j = i + 1; j < n; )
//        {
//            int left = j + 1;
//            int right = n - 1;
//            while (left < right)
//            {
//                long long aim = (long long)target - nums[i] - nums[j];
//                if (left < right && nums[left] + nums[right] < aim) ++left;
//                else if (left < right && nums[left] + nums[right] > aim) --right;
//                else {
//                    vector<int> tmp{ nums[i], nums[j], nums[left], nums[right] };
//                    vv.push_back(tmp);
//                    do
//                    {
//                        ++left;
//                    } while (left < right && nums[left] == nums[left - 1]);
//                    do
//                    {
//                        --right;
//                    } while (left < right && nums[right] == nums[right + 1]);
//                }
//            }
//            do
//            {
//                ++j;
//            } while (j < n && nums[j] == nums[j - 1]);
//        }
//        do
//        {
//            ++i;
//        } while (i < n && nums[i] == nums[i - 1]);
//    }
//    return vv;
//}


